/*https://leetcode.cn/problems/longest-increasing-subsequence/submissions/562784892/
最长递增子序列
25/9/5
*/
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        // 首先对数组进行排序
        sort(nums.begin(), nums.end());

        // 使用一个向量来存储每个数字及其累积值（即该数字出现次数乘以其值）
        vector<pair<int, int>> numValues;
        int index = 1, occurrenceCount = 1; // 初始化索引和计数器

        // 遍历排序后的数组，计算每个不同数字的累积值
        for (; index < nums.size(); ++index) {
            if (nums[index] != nums[index - 1]) { // 如果当前数字与前一个不同
                numValues.emplace_back(nums[index - 1], nums[index - 1] * occurrenceCount); // 存储数字及其累积值
                occurrenceCount = 1; // 重置计数器
            } else {
                occurrenceCount++; // 同一数字出现次数增加
            }
        }
        // 添加最后一个数字及其累积值
        numValues.emplace_back(nums[index - 1], nums[index - 1] * occurrenceCount);

        // 动态规划部分
        index = 1;
        int twoStepsBack = 0, oneStepBack = numValues[0].second, result = oneStepBack; // 初始化动态规划变量
        for (; index < numValues.size(); ++index) {
            if (numValues[index].first == numValues[index - 1].first + 1) {
                // 如果当前数字是前一个数字的直接后继，则需要在放弃前一个数字的收益或选择当前数字的收益之间做出选择
                result = max(twoStepsBack + numValues[index].second, oneStepBack);
            } else {
                // 如果当前数字不是前一个数字的直接后继，则可以选择当前数字和前一个数字的收益
                result = oneStepBack + numValues[index].second;
            }
            // 更新动态规划变量
            twoStepsBack = oneStepBack;
            oneStepBack = result;
        }

        // 返回最终结果
        return result;
    }
};